package com.example.demo.leetcode.zuocheng.sort;

/**
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/7/24 15:35
 */
public class Arr_计数排序 {

    public static void main(String[] args) {

        int [] arr = {23,45,66,66,1,2,44};

        int[] sort = sort(arr, getMax(arr));
        for(int i =0 ;i<sort.length;i++){
            System.out.println(sort[i]);
        }
    }

    public static int getMax(int [] arr){

        int max = 0;
        for(int i =0 ;i<arr.length;i++){
            max = Math.max(max,arr[i]);
        }
        return max;
    }

    public static int [] sort(int [] arr,int max){

        int [] result = new int [arr.length];
        int [] count = new int[max+1];
        for(int i =0;i<arr.length;i++){
            count[arr[i]]++;
        }

        for(int i=0,j=0;i<count.length;i++){
            while(count[i] > 0){
                result[j] = i;
                count[i]--;
                j++;
            }
        }
        return  result;
    }

}
